package com.chao.sort;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description :
 * @date : 2023/7/4
 */
public class BubbleSort {

    public static void main(String[] args) {
        int []arr = new int[] {3,8,2,4,1,5,9};
        cocktailSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    private static void sort(int []arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 -i; j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }
            }
        }   
    }

    private static void optimizeSort(int []arr) {
        boolean swaped;
        for (int i = 0; i < arr.length; i++) {
            swaped = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                    swaped = true;
                }
            }

            if (!swaped) {
                // 一轮比较完 元素顺序未发生变化 说明数组已经有序
                break;
            }
        }
    }

    // 鸡尾酒排序
    private static void cocktailSort(int []arr) {
        int start = 0,end = arr.length - 1;
        boolean swaped;
        while (start < end) {
            swaped = false;
            for (int i = start; i < end; i++) {
                if (arr[i] > arr[i+1]) {
                    swap(arr,i,i+1);
                    swaped = true;
                }
            }

            if (!swaped) {
                break;
            }
            end--;
            swaped = false;

            for (int i = end - 1; i >= start; i--) {
                if (arr[i] > arr[i+1]) {
                    swap(arr,i,i+1);
                    swaped = true;
                }
            }

            if (!swaped) {
                break;
            }
            start++;
        }
    }

    private static void swap(int []arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
